
#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define _DEBUG

#define MAX(a, b) ((a) > (b) ? (a) : (b))

char *addBinary(char *a, char *b) {
  char *res;
  int la = strlen(a);
  int lb = strlen(b);
  int lr = MAX(la, lb) + 1;
  res = (char *)malloc(lr + 1);
#ifdef _DEBUG
  memset(res, '0', lr);
#endif
  res[lr] = '\0';
  *res = '0';
  int advance = 0;
  for (int ia = la - 1, ib = lb - 1, ir = lr - 1; ia >= 0 || ib >= 0;
       ia--, ib--, ir--) {
    int na = ia >= 0 && a[ia] == '1';
    int nb = ib >= 0 && b[ib] == '1';
    int nres = advance + na + nb;
    res[ir] = nres % 2 + '0';
    advance = nres / 2;
  }
  if (advance) {
    res[0] = '1';

  } else {
    memcpy(res, res + 1, lr);
    res = (char *)realloc(res, lr);
    res[lr - 1] = 0;
  }
  return res;
}

int main() {
  printf("%s\n", addBinary("10101", "1011"));
  return 0;
}